package cn.demoncat.util.lang.entity.data;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.function.Consumer;

import cn.demoncat.util.exception.ParamRuntimeException;
import cn.demoncat.util.lang.ArrayUtil;
import cn.demoncat.util.lang.CollectionUtil;
import cn.demoncat.util.lang.constant.StringConstant;
import cn.demoncat.util.lang.fn.Function2;

/**
 * 图：邻接表，无向图
 * 
 * @author 延晓磊
 *
 * @since 2020年7月25日
 */
public class LinkedGraph<K extends Comparable<K>,V,W extends Comparable<W>> {

	/**
	 * 顶点集
	 */
	private final Map<K, V> vertexes;
	/**
	 * 边集（邻接表）
	 */
	private final Map<K, LinkedList<WeightData<K, W>>> edges;
	/**
	 * 边数
	 */
	private int edgeCount;
	
	/**
	 * 构建
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月25日
	 */
	public LinkedGraph() {
		super();
		this.vertexes = new LinkedHashMap<>();
		this.edges = new LinkedHashMap<>();
		this.edgeCount = 0;
	}

	/**
	 * 顶点集
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月25日
	 */
	public Map<K, V> getVertexes() {
		return vertexes;
	}
	
	/**
	 * 添加顶点
	 * 
	 * @param key
	 * @param data
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月25日
	 */
	public void addVertex(K key, V data) {
		// 顶点
		vertexes.put(key, data);
		// 边
		edges.put(key, new SingleLinkedList<>());
	}
	
	/**
	 * 添加顶点
	 * 
	 * @param key	键/值（类型相同）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月25日
	 */
	@SuppressWarnings("unchecked")
	public void addVertex(K key) {
		// 顶点
		vertexes.put(key, (V)key);
		// 边
		edges.put(key, new SingleLinkedList<>());
	}
	
	/**
	 * 顶点
	 * 
	 * @param key
	 * 
	 * @return data
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public V getVertexe(K key) {
		return vertexes.get(key);
	}
	
	/**
	 * 修改顶点（不存在时忽略）
	 * 
	 * @param key
	 * @param data
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public void setVertex(K key, V data) {
		if (vertexes.containsKey(key)) {
			vertexes.put(key, data);
		}
	}

	/**
	 * 顶点数
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public int getVertexSize() {
		return vertexes.size();
	}
	
	/**
	 * 边集（邻接表）
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public Map<K, LinkedList<WeightData<K, W>>> getEdges() {
		return edges;
	}
	
	/**
	 * 获取边列表（单向连接）
	 * 
	 * @return [{起点K，终点K，权重}]
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月29日
	 */
	public List<Edge<K,W>> getEdgeList(){
		List<Edge<K,W>> list = new ArrayList<>(edgeCount);
		List<K> visits = new ArrayList<>(edgeCount);
		// 遍历顶点
		for (K vertexe : vertexes.keySet()) {
			// 遍历顶点的边
			for (WeightData<K, W> wd : edges.get(vertexe)) {
				// 排除逆向连接
				if (!visits.contains(wd.getData())) {
					// 顺序连接
					if (vertexe.compareTo(wd.getData()) > 0) {
						list.add(new Edge<>(wd.getData(), vertexe, wd.getWeight()));
					} else {
						list.add(new Edge<>(vertexe, wd.getData(), wd.getWeight()));
					}
				}
			}
			// 已处理
			visits.add(vertexe);
		}
		return list;
	}
	
	/**
	 * 边的权值
	 * 
	 * @param k1	顶点1的key
	 * @param k2	顶点2的key 
	 * 
	 * @return 边的权值
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public W getWeight(K k1, K k2) {
		// 查询顶点
		if (!vertexes.containsKey(k1) || !vertexes.containsKey(k2)) {
			throw new RuntimeException("顶点不存在：v1 = " + vertexes.get(k1) + ", v2 = " + vertexes.get(k2)) ;
		}
		// 查询邻接表
		WeightData<K,W> wd = edges.get(k1).search(o -> o.getData().equals(k2));
		if (wd == null) {
			return null;
		}
		// 返回权值
		return wd.getWeight();
	}
	
	/**
	 * 设置边
	 * 
	 * @param k1		顶点1的key
	 * @param k2		顶点2的key 
	 * @param weight	边的权值：null表示删除，非null表示添加/修改
	 * 
	 * @return 旧的权值
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public W setEdge(K k1, K k2, W weight) {
		// 当前权值
		W curr = getWeight(k1, k2);
		// 操作类型
		if (curr == null) {
			if (weight != null) {
				// null > 非0 = 添加
				edges.get(k1).add(new WeightData<>(k2, weight));
				edges.get(k2).add(new WeightData<>(k1, weight));
				edgeCount ++;
			}
		}else {
			if (weight == null) {
				// 非null > null = 删除
				edges.get(k1).remove(o -> o.getData().equals(k2));
				edges.get(k2).remove(o -> o.getData().equals(k1));
				edgeCount --;
			}else {
				// 非null > 非null = 修改
				edges.get(k1).search(o -> o.getData().equals(k1)).setWeight(weight);
				edges.get(k2).search(o -> o.getData().equals(k2)).setWeight(weight);
			}
		} 
		return curr;
	}
	
	/**
	 * 删除边
	 * 
	 * @param k1		顶点1的key
	 * @param k2		顶点2的key 
	 * 
	 * @return 旧的权值
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public W delEdge(K k1, K k2) {
		return setEdge(k1, k2, null);
	}
	
	/**
	 * 边数
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public int getEdgeCount() {
		return edgeCount;
	}

	/**
	 * 显示图形（数组+链表）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public void show() {
		for (Entry<K, LinkedList<WeightData<K, W>>> entry : edges.entrySet()) {
			// 顶点key
			System.out.print(entry.getKey() + "\t");
			// 边
			for (WeightData<K, W> wd : entry.getValue()) {
				System.out.print("-> " + wd.getData() + "\t");
			}
			System.out.println(StringConstant.NEW_LINE);
		}
	}
	
	/**
	 * 获取第一个邻接顶点
	 * 
	 * @param key	顶点key
	 * 
	 * @return	邻接顶点key
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public K getFirstNeighbor(K key) {
		WeightData<K, W> first = edges.get(key).first();
		if (first == null) {
			return null;
		}
		return first.getData();
	}
	
	/**
	 * 获取下一个邻接顶点
	 * 
	 * @param key	顶点key
	 * @param curr	当前邻接顶点key
	 * 
	 * @return	邻接顶点key
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public K getNextNeighbor(K key, K curr) {
		boolean flag = false;
		for (WeightData<K, W> wd : edges.get(key)) {
			if (flag) {
				// 下一个邻接顶点
				return wd.getData();
			}else {
				// 找到当前邻接顶点
				if (wd.getData().equals(curr)) {
					flag = true;
				}
			}
		}
		return null;
	}
	
	/**
	 * 遍历 - 深度优先搜索（Depth First Search）
	 * 
	 * @param fn	消费（顶点）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public void dfs(Consumer<V> fn) {
		// 访问标识
		Map<K,Boolean> visits = new HashMap<>();
		for (K key : vertexes.keySet()) {
			visits.put(key, false);
		}
		// 遍历顶点，逐个挖掘
		for (K key : vertexes.keySet()) {
			if (!visits.get(key)) {
				dfs(visits, key, fn);
			}
		}
	}
	
	/**
	 * 遍历 - 深度优先搜索（Depth First Search）
	 * 
	 * @param visits	访问标识
	 * @param key		当前顶点key
	 * @param fn		消费（顶点）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	private void dfs(Map<K,Boolean> visits, K key, Consumer<V> fn) {
		// 消费当前顶点
		fn.accept(vertexes.get(key));
		// 设置为已访问
		visits.put(key, true);
		// 查找第一个邻接顶点
		K w = getFirstNeighbor(key);
		while (w != null) {
			// 未访问
			if (!visits.get(w)) {
				// 邻接顶点作为初始顶点，纵向递归挖掘
				dfs(visits, w, fn);
			}
			// 查找下一个邻接顶点
			w = getNextNeighbor(key, w);
		}
	}
	
	/**
	 * 遍历 - 广度优先搜索（Broad First Search）
	 * 
	 * @param fn	消费（顶点）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public void bfs(Consumer<V> fn) {
		// 访问标识
		Map<K,Boolean> visits = new HashMap<>();
		for (K key : vertexes.keySet()) {
			visits.put(key, false);
		}
		// 遍历顶点，逐个挖掘
		for (K key : vertexes.keySet()) {
			if (!visits.get(key)) {
				bfs(visits, key, fn);
			}
		}
	}
	
	/**
	 * 遍历 - 广度优先搜索（Broad  First Search）
	 * 
	 * @param visits	访问标识
	 * @param key		当前顶点索引
	 * @param fn		消费（顶点）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	private void bfs(Map<K,Boolean> visits, K key, Consumer<V> fn) {
		// 队列头
		K u;
		// 邻接顶点
		K w;
		// 队列
		Queue<K> queue = new ArrayQueue<>(vertexes.size());
		
		// 消费当前顶点
		fn.accept(vertexes.get(key));
		// 设置为已访问
		visits.put(key, true);
		// 加入队列
		queue.add(key);
		
		while (!queue.isEmpty()) {
			// 取出队列头
			u = queue.get();
			// 查找第一个邻接顶点
			w = getFirstNeighbor(u);
			while (w != null) {
				// 未访问
				if (!visits.get(w)) {
					// 消费当前顶点
					fn.accept(vertexes.get(w));
					// 设置为已访问
					visits.put(w, true);
					// 加入队列
					queue.add(w);
				}
				// 逐层，横向循环挖掘
				w = getNextNeighbor(u, w);
			}
		}
	}
	
	/**
	 * 获取连通图的最小生成树 （普里姆算法 - 适合稠密的连通网）
	 * 
	 * @return 最小生成树的边
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月28日
	 */
	public List<Edge<K,W>> getMstByPrim(){
		return getMstByPrim(null);
	}
	
	/**
	 * 获取连通图的最小生成树 （普里姆算法 - 适合稠密的连通网）
	 * 
	 * @param start	起始顶点（如果为空就随机获取）
	 * 
	 * @return 最小生成树的边
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月28日
	 */
	public List<Edge<K,W>> getMstByPrim(K start){
		// 起始顶点
		if (start == null) {
			for (K key : vertexes.keySet()) {
				start = key;
				break;
			}
		}
		// 已选顶点
		List<K> selects = new ArrayList<>();
		selects.add(start);
		// 最小权值
		W min = null;
		K end = null;
		// 循环，找出n-1条最小的边
		List<Edge<K,W>> result = new ArrayList<>(vertexes.size() - 1);
		for (int i = 1; i < vertexes.size(); i++) {
			// 遍历已选顶点
			for (K curr : selects) {
				// 遍历顶点的边
				for (WeightData<K, W> wd : edges.get(curr)) {
					// 未选取，权值更小
					if (!selects.contains(wd.getData()) && (min == null || wd.getWeight().compareTo(min) < 0)) {
						start = curr;
						end = wd.getData();
						min = wd.getWeight(); 
					}
				}
			}
			// 保存最小的边
			if (end == null) {
				throw new ParamRuntimeException("连通图中不能包含未连通的顶点");
			}else {
				// 保存边
				result.add(new Edge<>(start, end, min));
				// 选择顶点
				selects.add(end);
				// 清空，继续查找
				end = null;
				min = null;
			}
		}
		return result;
	}
	
	/**
	 * 获取连通图的最小生成树 （克鲁斯卡尔算法 - 适合稀疏的连通网）
	 * 
	 * @return 最小生成树的边
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月29日
	 */
	public List<Edge<K,W>> getMstByKruskal(){
		// 收集所有边，以升序排列
		List<Edge<K, W>> es = CollectionUtil.sort(getEdgeList());
		// 依次加入最小生成树（以n-1条边连通所有顶点），如果存在回路则跳过
		List<Edge<K,W>> result = new ArrayList<>(vertexes.size() - 1);
		Map<K,Integer> sects = new HashMap<>();
		Integer startSect;
		Integer endSect;
		Integer seat = 0;
		for (Edge<K,W> e : es) {
			// 起点.门派
			startSect = sects.get(e.getStart());
			// 终点.门派
			endSect = sects.get(e.getEnd());
			// 判断回路（起点和终点属于相同门派则连通）
			if (startSect == null || !startSect.equals(endSect)) {
				// 加入最小生成树
				result.add(e);
				// 回路标记（将连通的顶点设置为相同的门派）
				if (startSect == null && endSect == null) {
					// 起点门派 == 终点门派 => 新门派
					seat++;
					sects.put(e.getStart(), seat);
					sects.put(e.getEnd(), seat);
				}else if(startSect == null) {
					// 起点门派 => 终点门派
					sects.put(e.getStart(), endSect);
				}else if(endSect == null) {
					// 终点门派 => 起点门派
					sects.put(e.getEnd(), startSect);
				}else {
					// 合并门派
					for (Entry<K, Integer> entry : sects.entrySet()) {
						if (entry.getValue().equals(endSect)) {
							entry.setValue(startSect);
						}
					}
				}
			}
		}
		return result;
	}
	
	/**
	 * 计算顶点start到其它各顶点的最短路径（迪杰斯特拉算法）
	 * 
	 * @param start	起始顶点
	 * @param adder	加法器
	 * 
	 * @return 结果数据
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月30日
	 */
	public DijkstraData getWaysByDijkstra(K start, Function2<W, W, W> adder) {
		// 统计数据
		DijkstraData data = new DijkstraData(start);
		// 计算邻接顶点的权值
		computeMinWeight(data, start, adder);
		// 计算中转顶点的权值
		for(int i = 1; i < vertexes.size(); i++) {
			computeMinWeight(data, data.getMinEnd(), adder);
		}
		return data;
	}
	
	
	/**
	 * 计算当前顶点到邻接顶点的权值，得出起始顶点到这些顶点的最短权值
	 * 
	 * @param data
	 * @param key	当前顶点
	 * @param adder	加法器：起始顶点到当前顶点的权值 + 当前顶点到邻接顶点的权值 = 中转权值
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月30日
	 */
	private void computeMinWeight(DijkstraData data, K key, Function2<W, W, W> adder) {
		// 访问当前顶点
		data.visit(key);
		// 起始顶点到当前顶点的权值
		W currWeight = data.getWeight(key);
		// 广度遍历
		W weight, endWeight;
		for (WeightData<K, W> wd : edges.get(key)) {
			if (!data.isVisit(wd.getData())){
				// 起始顶点到邻接顶点的当前权值
				endWeight = data.getWeight(wd.getData());
				// 中转权值：起始顶点到当前顶点的权值 + 当前顶点到邻接顶点的权值
				weight = currWeight == null ? wd.getWeight() : adder.apply(currWeight, wd.getWeight());
				// 中转权值 < 当前权值 = 替换
				if (endWeight == null || weight.compareTo(endWeight) < 0) {
					// 设置起始顶点到邻接顶点的权值
					data.setWeight(wd.getData(), weight);
					// 设置邻接顶点的前驱
					data.setPre(wd.getData(), key);
				}
			}
		}
	}
	
	/**
	 * 迪杰斯特拉算法的操作数据
	 * 
	 * 功能：计算顶点到其它各顶点的最短路径
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月30日
	 */
	public class DijkstraData{
		
		// 起始顶点
		private final K start;
		// 已访问的顶点
		private final List<K> visits;
		// 起始顶点到其它顶点的权值
		private final Map<K,W> weights;
		// 其它顶点的前驱（逆推路径）
		private final Map<K,K> pres;
	
		/**
		 * 构建
		 * 
		 * @param start	起始顶点
		 * 
		 * @author 延晓磊
		 *
		 * @since 2020年7月31日
		 */
		private DijkstraData(K start) {
			super();
			this.start = start;
			visits = new ArrayList<>();
			weights = new HashMap<>();
			pres = new HashMap<>();
		}
		
		/**
		 * 获取起始顶点
		 * 
		 * @return
		 * 
		 * @author 延晓磊
		 *
		 * @since 2020年7月30日
		 */
		public K getStart() {
			return start;
		}
	
		/**
		 * 获取路径权值
		 * 
		 * @param end	终点
		 * @return
		 * 
		 * @author 延晓磊
		 *
		 * @since 2020年7月30日
		 */
		public W getWeight(K end) {
			return weights.get(end);
		}
		
		/**
		 * 获取路径权值集
		 * 
		 * @return {终点:权值}
		 * 
		 * @author 延晓磊
		 *
		 * @since 2020年7月30日
		 */
		public Map<K,W> getWeights(){
			return weights;
		}
		
		/**
		 * 获取前驱（逆推路径）
		 * 
		 * @param end	终点
		 * 
		 * @return
		 * 
		 * @author 延晓磊
		 *
		 * @since 2020年7月30日
		 */
		public K getPre(K end){
			return pres.get(end);
		}
		
		/**
		 * 获取前驱集（逆推路径）
		 * 
		 * @return
		 * 
		 * @author 延晓磊
		 *
		 * @since 2020年7月30日
		 */
		public Map<K,K> getPres(){
			return pres;
		}
		
		/**
		 * 获取路径
		 * 
		 * @param end	终点
		 * 
		 * @author 延晓磊
		 * @return 
		 *
		 * @since 2020年7月30日
		 */
		public Way<K, W> getWay(K end) {
			// 查询路径
			W weight = getWeight(end);
			if (weight == null) {
				return null;
			}
			// 总路线
			Way<K,W> way = new Way<>(start, end, weight);
			K curr = end;
			K pre = getPre(curr);
			// 中转路线
			if (!start.equals(pre)) {
				while (pre != null) {
					// 添加中转路线
					way.first(new Edge<>(pre, curr, LinkedGraph.this.getWeight(pre, curr)));
					// 逆推
					curr = pre;
					pre = getPre(curr);
				}
			}
			return way;
		}
		
		/**
		 * 获取路径集
		 * 
		 * @author 延晓磊
		 * @return 
		 *
		 * @since 2020年7月30日
		 */
		public List<Way<K, W>> getWays() {
			List<Way<K,W>> list = new ArrayList<>(weights.size());
			// 转换路径
			Way<K,W> way;
			K pre;
			K curr;
			for (Entry<K, W> entry : weights.entrySet()) {
				// 总路线
				way = new Way<>(start, entry.getKey(), entry.getValue());
				list.add(way);
				// 中转路线
				curr = entry.getKey();
				pre = getPre(curr);
				if (!start.equals(pre)) {
					while (pre != null) {
						// 添加中转路线
						way.first(new Edge<>(pre, curr, LinkedGraph.this.getWeight(pre, curr)));
						// 逆推
						curr = pre;
						pre = getPre(curr);
					}
				}
			}
			// 权值升序
			Collections.sort(list);
			return list;
		}
		
		/**
		 * 判断是否访问过顶点
		 * 
		 * @param end	顶点
		 * @return
		 * 
		 * @author 延晓磊
		 *
		 * @since 2020年7月30日
		 */
		private boolean isVisit(K end) {
			return visits.contains(end);
		}
		
		/**
		 * 设置顶点为已访问
		 * 
		 * @param end	顶点
		 * 
		 * @author 延晓磊
		 *
		 * @since 2020年7月30日
		 */
		private void visit(K end) {
			visits.add(end);
		}
		
		/**
		 * 设置起始顶点到终点的权值
		 * 
		 * @param end		终点
		 * @param weight	权值
		 * 
		 * @author 延晓磊
		 *
		 * @since 2020年7月30日
		 */
		private void setWeight(K end, W weight) {
			weights.put(end, weight);
		}
		
		/**
		 * 设置终点的前驱
		 * 
		 * @param end	终点
		 * @param pre	前驱
		 * 
		 * @author 延晓磊
		 *
		 * @since 2020年7月30日
		 */
		private void setPre(K end, K pre) {
			pres.put(end, pre);
		}
		
		/**
		 * 获取权值最小的终点
		 * 
		 * @author 延晓磊
		 *
		 * @since 2020年7月30日
		 */
		private K getMinEnd() {
			W min = null;
			K key = null;
			for (Entry<K, W> entry : weights.entrySet()) {
				if (!isVisit(entry.getKey())) {
					if (min == null || entry.getValue().compareTo(min) < 0) {
						min = entry.getValue();
						key = entry.getKey();
					}
				}
			}
			return key;
		}
	}
	
	/**
	 * 计算每个顶点到其它各顶点的最短路径（弗洛伊德算法）
	 * 
	 * @param zero	0
	 * @param adder	加法器
	 * 
	 * @return 结果数据
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月30日
	 */
	public FloydData getWaysByFloyd(W zero, Function2<W, W, W> adder) {
		return new FloydData(zero).compute(adder);
	}
	
	/**
	 * 弗洛伊德算法的操作数据
	 * 
	 * 功能：计算各顶点到其它各顶点的最短路径
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月30日
	 */
	public class FloydData{
		
		// 顶点
		private K[] vs = null;
		// 边：各顶点到其它顶点的权值
		private final W[][] weights;
		// 前驱：各顶点到其它顶点的前驱（逆推路径）
		private final int[][] pres;
		
		/**
		 * 获取路径权值
		 * 
		 * @param start	起点
		 * @param end	终点
		 * @return
		 * 
		 * @author 延晓磊
		 *
		 * @since 2020年7月30日
		 */
		public W getWeight(K start, K end) {
			return weights[getIndex(start)][getIndex(end)];
		}
		
		/**
		 * 获取路径权值集
		 * 
		 * @param start 起点
		 * 
		 * @return {终点:权值}
		 * 
		 * @author 延晓磊
		 *
		 * @since 2020年7月30日
		 */
		public Map<K,W> getWeights(K start){
			int index = getIndex(start);
			Map<K,W> map = new HashMap<>();
			for (int i = 0; i < vs.length; i++) {
				if (index != i) {
					map.put(vs[i], weights[index][i]);
				}
			}
			return map;
		}
		
		/**
		 * 获取路径权值集
		 * 
		 * @return {起点：{终点:权值}}
		 * 
		 * @author 延晓磊
		 *
		 * @since 2020年7月31日
		 */
		public Map<K,Map<K,W>> getWeights(){
			Map<K,Map<K,W>> maps = new HashMap<>();
			Map<K,W> map;
			int index;
			for (K start : vs) {
				map = new HashMap<>();
				index = getIndex(start);
				for (int i = 0; i < vs.length; i++) {
					if (index != i) {
						map.put(vs[i], weights[index][i]);
					}
				}
				maps.put(start, map);
			}
			return maps;
		}
		
		/**
		 * 获取前驱（逆推路径）
		 * 
		 * @param start	起点
		 * @param end	终点
		 * 
		 * @return
		 * 
		 * @author 延晓磊
		 *
		 * @since 2020年7月30日
		 */
		public K getPre(K start, K end){
			return vs[pres[getIndex(start)][getIndex(end)]];
		}
		
		/**
		 * 获取路径
		 * 
		 * @param start	起点
		 * @param end	终点
		 * 
		 * @author 延晓磊
		 * @return 
		 *
		 * @since 2020年7月30日
		 */
		public Way<K, W> getWay(K start, K end) {
			// 查询路径
			W weight = getWeight(start, end);
			if (weight == null) {
				return null;
			}
			// 总路线
			Way<K,W> way = new Way<>(start, end, weight);
			int index = getIndex(start);
			K curr = end;
			K pre = vs[pres[index][getIndex(curr)]];
			// 中转路线
			if (!start.equals(pre)) {
				while (!curr.equals(pre)) {
					// 添加中转路线
					way.first(new Edge<>(pre, curr, LinkedGraph.this.getWeight(pre, curr)));
					// 逆推
					curr = pre;
					pre = vs[pres[index][getIndex(curr)]];
				}
			}
			return way;
		}
		
		/**
		 * 获取路径集
		 * 
		 * @param start	起点
		 * 
		 * @author 延晓磊
		 * @return 
		 *
		 * @since 2020年7月30日
		 */
		public List<Way<K, W>> getWays(K start) {
			List<Way<K,W>> list = new ArrayList<>(vs.length -1);
			// 转换路径
			Way<K,W> way;
			K pre;
			K curr;
			int index = getIndex(start);
			for (int i = 0; i < vs.length; i++) {
				if (index != i) {
					// 总路线
					way = new Way<>(start, vs[i], weights[index][i]);
					list.add(way);
					// 中转路线
					curr = vs[i];
					pre = vs[pres[index][i]];
					if (!start.equals(pre)) {
						while (!curr.equals(pre)) {
							// 添加中转路线
							way.first(new Edge<>(pre, curr, LinkedGraph.this.getWeight(pre, curr)));
							// 逆推
							curr = pre;
							pre = vs[pres[index][getIndex(curr)]];
						}
					}
				}
			}
			// 权值升序
			Collections.sort(list);
			return list;
		}
		
		/**
		 * 获取路径集
		 * 
		 * @author 延晓磊
		 * @return 
		 *
		 * @since 2020年7月30日
		 */
		public Map<K,List<Way<K, W>>> getWays() {
			Map<K,List<Way<K, W>>> map = new HashMap<>();
			for (K k : vs) {
				map.put(k, getWays(k));
			}
			return map;
		}
		
		/**
		 * 构建
		 * 
		 * 因为所有顶点互通，同时便于检索，所以转换为邻接矩阵进行计算
		 * 
		 * @param zero 0
		 * 
		 * @author 延晓磊
		 *
		 * @since 2020年7月31日
		 */
		private FloydData(W zero) {
			super();
			// 顶点
			for (K k : vertexes.keySet()) {
				vs = ArrayUtil.instance(k.getClass(), vertexes.size());
				break;
			}
			int i = 0;
			for (K k : vertexes.keySet()) {
				vs[i++] = k;
			}
			ArrayUtil.quickSort(vs);
			// 边
			weights = ArrayUtil.instance2(zero.getClass(), vertexes.size(), vertexes.size());
			for (Entry<K, LinkedList<WeightData<K, W>>> entry : edges.entrySet()) {
				// 起点
				i = getIndex(entry.getKey());
				weights[i][i] = zero;
				for (WeightData<K, W> wd : entry.getValue()) {
					// 终点
					weights[i][getIndex(wd.getData())] = wd.getWeight();
				}
			}
			// 前驱（下标）
			pres = new int[vertexes.size()][vertexes.size()];
			for (i = 1; i < pres.length; i++) {
				Arrays.fill(pres[i], i);
			}
		}
		
		/**
		 * 计算最短路径
		 * 
		 * @param adder	加法器
		 * @return
		 * 
		 * @author 延晓磊
		 *
		 * @since 2020年7月31日
		 */
		private FloydData compute(Function2<W, W, W> adder) {
			W w, ab, bc, ac;
			// 中转顶点
			for (int b = 0; b < vs.length; b++) {
				// 出发顶点
				for (int a = 0; a < vs.length; a++) {
					// 目标顶点
					for (int c = 0; c < vs.length; c++) {
						// 出发到中转
						ab = weights[a][b];
						if (ab == null) {
							break;
						}
						// 中转到目标
						bc = weights[b][c];
						if (bc == null) {
							break;
						}
						// 出发到目标：ab + bc
						w = adder.apply(ab, bc);
						// 选取最短路径
						ac = weights[a][c];
						if (ac == null || w.compareTo(ac) < 0) {
							weights[a][c] = w;
							pres[a][c] = pres[b][c];
						}
					}
				}
			}
			return this;
		}
		
		/**
		 * 获取顶点的索引
		 * 
		 * @param k
		 * @return
		 * 
		 * @author 延晓磊
		 *
		 * @since 2020年7月31日
		 */
		private int getIndex(K k) {
			return ArrayUtil.binarySearch(vs, k);
		}
	}
	
}
